package com.lenl.arithmetic.tenusablealgorithm.greedy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @author Lenl
 * @version v1.0
 * @create 2022-05-14 15:33
 * @description 贪心算法
 */
public class GreedyAlgorithm {
    public static void main(String[] args) {
        //创建广播电台，放入到Map
        HashMap<String, HashSet<String>> broadcasts=new HashMap<>();
        //将各个电台放入到broadcasts
        HashSet<String> hashSet1=new HashSet<>();
        hashSet1.add("北京");
        hashSet1.add("上海");
        hashSet1.add("天津");
        HashSet<String> hashSet2=new HashSet<>();
        hashSet2.add("广州");
        hashSet2.add("北京");
        hashSet2.add("深圳");
        HashSet<String> hashSet3=new HashSet<>();
        hashSet3.add("成都");
        hashSet3.add("上海");
        hashSet3.add("杭州");
        HashSet<String> hashSet4=new HashSet<>();
        hashSet4.add("上海");
        hashSet4.add("天津");

        HashSet<String> hashSet5=new HashSet<>();
        hashSet5.add("杭州");
        hashSet5.add("大连");

        //加入map
        broadcasts.put("k1",hashSet1);
        broadcasts.put("k2",hashSet2);
        broadcasts.put("k3",hashSet3);
        broadcasts.put("k4",hashSet4);
        broadcasts.put("k5",hashSet5);

        HashSet<String> allAreas=new HashSet<>();
        allAreas.add("北京");
        allAreas.add("上海");
        allAreas.add("天津");
        allAreas.add("广州");
        allAreas.add("深圳");
        allAreas.add("成都");
        allAreas.add("杭州");
        allAreas.add("大连");
        //创建一个arraylist，存放选择的电台集合
        ArrayList<String> selects=new ArrayList<>();
        //定义临时集合，保存在遍历过程中的电台覆盖的地区和尚未覆盖的地区的交集
        HashSet<String> tempSet=new HashSet<>();
        //保存在一次遍历过程中，能够覆盖最多未覆盖地区对应电台的key
        //如果不为空，则加入selects
        String maxKey=null;
        while(allAreas.size()!=0){
            //重置maxkey
            maxKey=null;
            //如果allAreas不为0，表明还未覆盖所有地区
            //遍历broadcasts，取出对应的key
            for (String key:broadcasts.keySet()){
                //重置缓冲set
                tempSet.clear();
                //当前这个key能覆盖的地区
                HashSet<String> areas= broadcasts.get(key);
                tempSet.addAll(areas);
                //求tempSet与allAreas的交集，会重新付给tempSet
                tempSet.retainAll(allAreas);
                //如果当前集合包含的未覆盖地区比maxkey指向的集合未覆盖的地区还多
                //就需要重置maxKey

                if(tempSet.size()>0){
                    HashSet<String> temp2=new HashSet<>();
                    if(maxKey!=null){
                        temp2.addAll(broadcasts.get(maxKey));
                        temp2.retainAll(allAreas);
                    }
                    //取交集最多的（贪心）
                    if(maxKey==null||tempSet.size()>temp2.size())
                        maxKey=key;
                }
            }
            //
            if(maxKey!=null){
                selects.add(maxKey);
                //将maxkey指向的广播电台覆盖的地区从allAreas中去掉
                allAreas.removeAll(broadcasts.get(maxKey));

            }
        }

        System.out.println("结果为："+selects);

    }
}
